//
// Description: 516. 最长回文子序列
// Created by Loading on 2021/8/12.
//

#include <bits/stdc++.h>

using namespace std;

int longestPalindromeSubseq(string s) {
    // dp 数组，dp[i][j] 表示在下标区间[i, j]中，最长回文子序列长度
    vector<vector<int>> dp(s.size(), vector<int>(s.size()));
    /* 注意：i 要逆序遍历，因为后续要使用 dp[i + 1][j - 1] 的值，顺序遍历会导致此值未计算 */
    for (int i = (int) s.size() - 1; i >= 0; --i) {
        // i 本身是一个长度为 1 的回文子序列
        dp[i][i] = 1;
        /* j 要顺序遍历 */
        for (int j = i + 1; j < s.size(); ++j) {
            if (s[j] == s[i]) {
                // 首尾值相同，取之间的最大长度 + 2，dp[i][j] 在当 i > j 时值为0，可以直接 + 2，无需特判
                dp[i][j] = max(dp[i][j], dp[i + 1][j - 1] + 2);
            } else {
                // 首尾值不同，取不加任意一端的 dp 最大值
                dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);
            }
        }
    }
    return dp[0][s.size() - 1];
}

int main() {
    string s = "baa";
    int res = longestPalindromeSubseq(s);
    cout << res << endl;
}